package BackTracking;//二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
//
// 请返回 封闭岛屿 的数目。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,
//0,1],[1,1,1,1,1,1,1,0]]
//输出：2
//解释：
//灰色区域的岛屿是封闭岛屿，因为这座岛屿完全被水域包围（即被 1 区域包围）。 
//
// 示例 2： 
//
// 
//
// 
//输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：grid = [[1,1,1,1,1,1,1],
//             [1,0,0,0,0,0,1],
//             [1,0,1,1,1,0,1],
//             [1,0,1,0,1,0,1],
//             [1,0,1,1,1,0,1],
//             [1,0,0,0,0,0,1],
//             [1,1,1,1,1,1,1]]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 1 <= grid.length, grid[0].length <= 100 
// 0 <= grid[i][j] <=1 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 127 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class closedIsland {

    int row,col;
    public int closedIsland(int[][] grid) {
        /**
         先将边界的岛屿全部置1，然后就类似于找岛屿数量题
         */
        row = grid.length;
        col = grid[0].length;
        for(int i=0;i<col;i++){
            //第一行和最后一行发现边界岛屿,将边界岛屿的所有岛屿置1
            if(grid[0][i]==0 || grid[row-1][i]==0){
                dfs(grid,0,i);
                dfs(grid,row-1,i);
            }
        }

        for(int i=0;i<row;i++){
            //第一列，最后一列,将边界岛屿的所有岛屿置1
            if(grid[i][0]==0 || grid[i][col-1]==0){
                dfs(grid,i,0);
                dfs(grid,i,col-1);
            }
        }
        int count = 0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                //发现岛屿再进入
                if(grid[i][j]==0){
                    count++;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    private void dfs(int[][] grid, int i, int j){
        if(i<0 || i>=row || j<0 || j>=col || grid[i][j]==1){
            return;
        }
        grid[i][j] = 1;

        dfs(grid, i - 1, j);//上
        dfs(grid, i + 1, j);//下
        dfs(grid, i, j + 1);//左
        dfs(grid, i, j - 1);//右
    }

}
//leetcode submit region end(Prohibit modification and deletion)
